# 希尔排序


def shell_sort(arr):
    n = len(arr)                              # 获取列表长度
    gap = n // 2                              # 初始增量设为数组长度的一半

    while gap > 0:
        for i in range(gap, n):                # 从gap位置开始遍历
            temp = arr[i]                      # 保存当前待插入元素
            j = i
            while j >= gap and arr[j - gap] > temp:       # 大小比较条件
                arr[j] = arr[j - gap]           # 大元素后移
                j -= gap
            arr[j] = temp                       #插入正确位置
        gap = gap // 2                          #增量减半
    return arr

print(shell_sort([55,662,11,5,34,88,999]))